import copy

grammar41 = {
    'terminals': {'s', 't', 'g', 'w', 'e', 'd'},
    'non_terminals': {'S', 'N', 'V'},
    'start': 'S',
    'productions': [
        ('S', ['N', 'V', 'N']),  # S :== NVN
        ('N', ['s']),  # N :== s|t|g|w
        ('N', ['t']),
        ('N', ['g']),
        ('N', ['w']),
        ('V', ['e']),  # V :== e|d
        ('V', ['d']),
    ]
}
print(grammar41)
SntStack = 'g,d,w'.split(',')  # 推导句子：gdw #句子栈
SntStack.reverse()
DeduceStack = ['S']  # 推导栈
print(SntStack)
print(DeduceStack)
ProdList = grammar41['productions']
print(ProdList)


def Deducting(DeduceStack, SntStack, productions):

    if len(SntStack) != 0 and len(DeduceStack) != 0:
        # 如果栈顶元素是非终结符且与句子不相等，则返回
        if (DeduceStack[-1] in grammar41['terminals']) and (SntStack[-1] != DeduceStack[-1]):
            return

        if SntStack[-1] == DeduceStack[-1]:  # 如果栈顶元素相等，则出栈
            SntStack.pop()
            DeduceStack.pop()
    if len(SntStack) == 0 and len(DeduceStack) == 0:  # 如果两个栈都为空，则推导成功
        print("Successful")
        return
    CurrSymbol = DeduceStack.pop()  # 当前符号
    for i in range(len(productions)):
        left, right = productions[i]
        if left == CurrSymbol:  # 如果当前符号与产生式左部相同
            NewDeduceStack = copy.deepcopy(DeduceStack)
            NewDeduceStack.extend(right)
            print(NewDeduceStack)
            NewSntStack = copy.deepcopy(SntStack)
            Deducting(NewDeduceStack, NewSntStack, productions)  # 递归调用


print('start deducting...')
Deducting(DeduceStack, SntStack, ProdList)
